#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        int ret = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            ret = max(ret, dp[i]);
            //cout<<i<<":"<<dp[i]<<endl;
        }
        return ret;
    }
};

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        //if(nums.size()==1)
            //return nums[0];
        int n = nums.size();
        vector<int> dp1(n, 0);
        dp1[0] = nums[0];
        int sum = nums[0];
        vector<int> dp2(dp1);
        //dp[0] = nums[0];
        int _max = nums[0];
        int _min = nums[0];
        for (int i = 1; i < n; i++)
        {
            dp1[i] = max(nums[i], dp1[i - 1] + nums[i]);
            _max = max(_max, dp1[i]);
            dp2[i] = min(nums[i], dp2[i - 1] + nums[i]);
            _min = min(_min, dp2[i]);
            //cout<<i<<":"<<dp2[i]<<endl;
            sum += nums[i];
        }
        if (sum == _min)
            return _max;
        return max(_max, sum - _min);
    }
};

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 0);
        f[0] = nums[0];
        vector<int> g(f);
        //dp[0][0] = dp[0][1] = nums[0];
        int ret = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = max(nums[i], f[i - 1] * nums[i]);
            f[i] = max(f[i], g[i - 1] * nums[i]);
            g[i] = min(nums[i], g[i - 1] * nums[i]);
            g[i] = min(g[i], f[i - 1] * nums[i]);
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 0);
        vector<int> g(n, 0);
        if (nums[0] > 0)
            f[0] = 1;
        else if (nums[0] < 0)
            g[0] = 1;
        int ret = f[0];

        for (int i = 1; i < n; i++)
        {
            if (nums[i] == 0)
                f[i] = g[i] = 0;
            else if (nums[i] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] != 0 ? g[i - 1] + 1 : 0;
            }
            else
            {
                f[i] = g[i - 1] != 0 ? g[i - 1] + 1 : 0;
                g[i] = f[i - 1] + 1;
            }
            cout << i << ":" << f[i] << " " << g[i] << endl;
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        vector<int> tmp(nums);
        int n = nums.size();
        for (int i = 1; i < n; i++)
        {
            tmp[i] = nums[i] - nums[i - 1];
        }
        vector<int> dp(n, 0);
        if (n == 1 || n == 2)
            return 0;
        int ret = 0;
        for (int i = 2; i < n; i++)
        {
            dp[i] = tmp[i] == tmp[i - 1] ? dp[i - 1] + 1 : 0;
            ret += dp[i];
            //cout<<tmp[i]<<" "<<tmp[i-1]<<" ";
            //cout<<i<<":"<<dp[i]<<endl;
        }
        return ret;
    }
};

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        if (arr.size() == 1)
            return 1;
        vector<int> dp(n, 1);
        int ret = 1;
        if (arr[1] != arr[0])
        {
            dp[1] = 2;
            ret = 2;
        }
        else
            dp[1] = 1;

        for (int i = 2; i < n; i++)
        {
            if ((long long)(arr[i] - arr[i - 1]) * (long long)(arr[i - 1] - arr[i - 2]) < 0)
                dp[i] = dp[i - 1] + 1;
            else
            {
                if (arr[i] != arr[i - 1])
                    dp[i] = 2;
                else
                    dp[i] = 1;
            }
            // cout<<i<<":"<<dp[i]<<endl;
            ret = max(dp[i], ret);
        }
        return ret;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        s = '1' + s;
        unordered_set<string> hash;
        for (auto& e : wordDict)
        {
            hash.insert(e);
        }
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j >= 1; j--)
            {
                if (dp[j - 1] == true && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];

    }
};

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int size = s.size();
        int arr[26] = { 0 };
        vector<int> dp(size, 1);
        arr[s[0] - 'a'] = 1;
        for (int i = 1; i < size; i++)
        {
            int index = s[i] - 'a';
            arr[index] = max(1, arr[index]);
            if (s[i - 1] + 1 == s[i] || s[i - 1] == 'z' && s[i] == 'a')
            {
                dp[i] = dp[i - 1] + 1;
                arr[index] = max(arr[index], dp[i]);
            }

        }
        int ret = 0;
        for (int i = 0; i < 26; i++)
            ret += arr[i];
        return ret;
    }
};